Trong lập trình, có khái niệm: một chương trình con (hàm, thủ tục) được gọi là đệ quy nếu trong quá trình thực hiện nó có phần phải gọi đến chính nó.

Cấu trúc chính

Một chương trình con đệ quy căn bản gồm hai phần.

• Phần cơ sở: chứa các tác động của hàm hoặc thủ tục với một số giá trị cụ thể ban đầu của tham số.
• Phần đệ quy: định nghĩa tác động cần được thực hiện cho giá trị hiện thời của các tham số bằng các tác động đã được định nghĩa trước đây với kích thước tham số nhỏ hơn.

Ví dụ: Hàm tính giai thừa của một số tự nhiên n (tính n ! {\displaystyle n!} ) (Đoạn mã sau được viết bằng ngôn ngữ Pascal)

  function gt(n: Word): Longint;  begin    if n = 1 then      gt:= 1    else      gt:= n * gt(n - 1);  end;

Quy trình thực hiện

Trong ví dụ trên, quy trình thực hiện như sau:

• Khi có lệnh gọi hàm, chẳng hạn:

 n:= gt(3);

• thì máy sẽ ghi nhớ là:

 gt(3):= 3 * gt(2);

và đi tính gt(2)

• kế tiếp máy lại ghi nhớ:

 gt(2):= 2 * gt(1);

và đi tính gt(1)

• Theo định nghĩa của hàm thì:

 gt(1):= 1;

• Máy sẽ quay ngược lại:

 gt(2):= 2 * 1;

cho kết quả là 2

• Tiếp tục:

 gt(3):= 3 * 2;

cho kết quả là 6

• Như vậy kết quả cuối cùng trả về là 6. Ta có: 3! = 6

Đệ quy tương hỗ

Nếu có hai chương trình con A1 và A2 gọi nhau ta có đệ quy tương hỗ.

Đệ quy tương hỗ thường được dùng để duyệt cây theo chiều sâu.

type B(...);type A(...){....    B(...);...}type B(...){....    A(...);...}